package 力扣._337_打家劫舍3;

import 力扣.公用数据结构.TreeNode;

public class Solution {
    //树形动规
    int[] robtree(TreeNode root) {
        //使用后序遍历，从叶节点向上依次选择要抢劫的对象
        //dp[i][0]: 不偷该节点的最大收获，dp[i][1]：偷该节点的最大收获 ，i标识当前递归层数
        if (root == null)
            return new int[]{0, 0};
        int[] left_dp = robtree(root.left);     //左子树
        int[] right_dp = robtree(root.right);   //右子树

        int v1 = root.val + left_dp[0] + right_dp[0];   //偷当前节点，则不偷左右孩子
        //不偷当前结点，则左右孩子偷不偷都可以
        int v2 = Math.max(left_dp[0], left_dp[1]) + Math.max(right_dp[0], right_dp[1]);
        return new int[]{v2, v1};
    }

    public int rob(TreeNode root) {
        int[] robtree = robtree(root);
        return Math.max(robtree[0], robtree[1]);
    }
}
